\frame{
	\tableofcontents
}


\section{Revisão}
\subsection{Aulas anteriores}
\frame{
	\frametitle{Revisão}
	\centerline{O que nós vimos até agora?}
	\begin{itemize}
		\item Esquemas clássicos de criptografia e suas vulnerabilidades
		\item Principais princípios da criptografia moderna
		\begin{enumerate}
			\item Princípio 1: Formulação de uma definição rigorosa
			e precisa de segurança
			\item Princípio 2: Premissas usadas em esquemas de segurança devem
			ser enunciadas precisamente
			\item Princípio 3: Construções criptográficas devem ser acompanhadas
			 de demonstrações rigorosas com respeito à definição
			de segurança, definida no princípio 1 e acompanhado das premissas
			afirmadas, pelo princípio 2, \textbf{se existirem}.
		\end{enumerate}
	\end{itemize}
}

\section{Introdução}

\frame{
	\frametitle{Introdução}
	\begin{itemize}
		\item Criptografica clássica
		\item Sigilo perfeito: Não há o uso do princípio 2, apenas do 1 e do 3
		\item Limitações práticas
		\item Base teórica para entender de fato a criptografia moderna
	\end{itemize}
}

\subsection{Definições}
\frame{
	\frametitle{Definições e propriedades básicas}
	
	Um esquema criptográfico é definido por três algoritmos
	\begin{enumerate}
		\item Gen: Tem natureza probabilística. Nos dá $k \in \mathcal{K}$
		\item Enc: Recebe como entrada  $k \in \mathcal{K}$ e uma mensagem $m \in \mathcal{M}$ e tem como saída
		um texto cifrado $c \in \mathcal{C}$. Denotamos o algoritmo como $Enc_k(m)$. Se o algoritmo for probabilístico,
		temos $c \gets Enc_k(m)$, se for determinístico, $c := Enc_k(m)$

		\item Dec: Recebe como entrada $c \in \mathcal{C}$ e $k \in \mathcal{K}$ e tem como saída $m \in \mathcal{M}$. Denotamos
		o algoritmo como $Dec_k(m)$. Podemos assumir Dec determinístico visto que assumimos esquemas
		criptográficos perfeitamente corretos: $Dec_k(Enc_k(m)) = m$

		\item $|\mathcal{K}| < \infty$
		\item $|\mathcal{M}| > 1$
	\end{enumerate}
}

\frame{
	\frametitle{Definições e propriedades básicas}
	\begin{enumerate}
		\item A probabilidade de uma chave ter o valor $k$ é denotada por $Pr[K=k]$
		\item A probabilidade de uma mensagem ter o valor $m$ é denotada por $Pr[M=m]$
		\item A probabilidade de um texto cifrado ter o valor $c$ é denotada por $Pr[C=c]$
		\item As distribuições de $\mathcal{K}$ e $\mathcal{M}$ são independentes: A chave é escolhida antes das mensagens serem enviadas!
		\item Dado o algoritmo $Enc$, a distribuição de $\mathcal{C}$ é determinada olhando para as distribuições de $\mathcal{M}$ e $\mathcal{K}$
	\end{enumerate}
}

\subsection{Sigilo perfeito}
\frame{
	\frametitle{Sigilo perfeito}
	\begin{block}{A ``definição'' de sigilo perfeito}
		Suponha que um adversário $\mathcal{A}$ conheça a distribuição de probabilidade de $\mathcal{M}$, ou seja, ele tem a idéia
		da probabilidade de determinada mensagem ocorrer. O adversário então $\mathcal{A}$ observa o texto cifrado. 

		Dizemos que um esquema
		criptográfico possui sigilo perfeito se a partir do texto cifrado um adversário não consegue obter nenhuma informação adicional do que já
		tinha sobre a probabilidade das mensagens, mesmo se esse tiver poder computacional ``ilimitado''.
		
		\bigskip 

		\color{red}{O texto cifrado não revela nada, absolutamente nada sobre o texto em claro que foi cifrado!}
	\end{block}

}

\frame{
	\frametitle{Sigilo perfeito}
	\begin{block}{A definição de sigilo perfeito}
		Um esquema criptográfico $\Pi = (Gen, Enc, Dec)$ sobre um espaço
		de mensagens $\mathcal{M}$ possui sigilo perfeito se para todas as distribuições
		de probabilidade de $\mathcal{M}$, para toda mensagem $m \in M$ e para todo texto cifrado
		$c \in C$ com $Pr[C=c]>0$:
		\begin{equation}
			Pr[M=m \,|\, C=c] = Pr[M=m]
		\end{equation}
	\end{block}

	\begin{block}{Nota dos autores}
		Por enquanto consideremos distribuições de probabilidade sobre $\mathcal{M}$ e sobre
		$\mathcal{C}$ que não atribuam probabilidade $0$ para algum $m\in \mathcal{M}$ ou $c \in \mathcal{C}$,
		isso evita uma possível divisão por zero.
		Não é uma grande limitação sobre os esquemas, visto que os teoremas que veremos servem para qualquer distribuição
		de probabilidade sobre $\mathcal{M}$ e $\mathcal{C}$.
	\end{block}

}

\frame{
	\frametitle{Outra definição de sigilo perfeito}
	\begin{block}{Lema}
		Um esquema criptográfico $\Pi = (Gen,Enc,Dec)$ sobre um espaço de mensagens $\mathcal{M}$ é
		perfeitamente sigiloso se, somente se, para toda distribuição de probabilidade sobre $\mathcal{M}$,
		toda mensagem $m \in \mathcal{M}$ e todo texto cifrado $c \in \mathcal{C}$ temos:
		\begin{equation}
			Pr[C=c \,|\, M=m] = Pr[C=c]
		\end{equation}
	\end{block}

	\vfill \onslide<2>{\centerline{\color{red}{Demonstração!}}}

}

\frame{
	 \frametitle{Indistinguibilidade perfeita}
	 \begin{block}{Indistinguibilidade perfeita}
		  Pelo lema anterior, podemos concluir que em um sistema criptográfico perfeito,
		  também temos a indistinguibilidade perfeita, isto é,  não conseguimos
		  diferenciar um texto cifrado de uma mensagem $m_0$ de um texto cifrado
		  de uma mensagem $m_1$.
	 \end{block}

}

\frame{
	\frametitle{Outra definição de sigilo perfeito (de novo!)}
	\begin{block}{Lema}
		Um esquema criptográfico $\Pi = (Gen,Enc,Dec)$ sobre um espaço de mensagem $\mathcal{M}$
		é perfeitamente sigiloso se, e se somente se, para toda distribuição de probabilidade
		sobre $\mathcal{M}$, para todo $m_0,m_1 \in \mathcal{M}$ e para todo $c \in \mathcal{C}$, temos:
		\begin{equation}
			Pr[C=c\,|\,M=m_0] = Pr[C=c\,|\,M=m_1]
		\end{equation}
	\end{block}
	 
	 \vfill{\onslide<2->{\centerline{\color{red}{Demonstração!}}}}
}

\subsection{Indistinguibilidade do adversário}
\frame{
	\frametitle{Indistinguibilidade do adversário}
	\begin{block}{Indistinguibilidade do adversário}
		Outra definição de sigilo perfeito é baseada em um experimento
		envolvendo um adversário $\mathcal{A}$, que formaliza a incapacidade
		de $\mathcal{A}$ distinguir um texto cifrado de um texto plano a partir
		de um texto cifrado de outro texto plano.

		\bigskip

		Formalmente, o experimento, denotado por $PrivK^{eav}_{\mathcal{A},\Pi}$, considera que
		a configuração é de cifragem com chave privada e o adversário, $\mathcal{A}$, observa o texto
		cifrado e que o esquema de criptografia é $\Pi = (Gen,Enc,Dec)$.
	\end{block}
}

\frame{
	\frametitle{Indistinguibilidade do adversário}
	\begin{block}{Indistinguibilidade do adversário}
	 O experimento é definido como:
		\begin{enumerate}
			\item O adversário escolhe duas mensagens, $m_0, m_1 \in \mathcal{M}$
			\item Uma chave aleatória é gerada por Gen, bem como um bit $b \gets{0,1}$ aleatório é escolhido 
		  (escolhidos por uma entidade que está rodando o experimento com o adversário).
			Então, o texto cifrado $c \gets Enc_k(m_b)$ é computado e dado à $\mathcal{A}$
			\item  $\mathcal{A}$ escolhe um bit $b'$
			\item A saída do experimento é $1$ se $b'=b$ e $0$ caso contrário. $PrivK^{eav}_{\mathcal{A},\Pi} = 1$
			se essa saída é $1$. Nesse caso dizemos que o adversário $\mathcal{A}$ teve sucesso
		\end{enumerate}
	\end{block}
}

\frame{
	\frametitle{Indistinguibilidade do adversário}

	$\mathcal{A}$ tenta adivinhar o valor de $b$. É sempre
        possível que $\mathcal{A}$ tenha sucesso
	no experimento com probabilidade de $\frac{1}{2}$ se escolher $b'$ aleatóriamente

	\bigskip

	\onslide<2->{\centerline{\color{red}{A questão é,	$\mathcal{A}$ pode fazer melhor que isso?}}}
  
	\onslide<3->{
	\begin{block}{Indistinguibilidade do adversário: equivalência}
		Um esquema criptográfico $\Pi = (Gen,Enc,Dec)$ sobre um espaço
		de mensagem $\mathcal{M}$ é perfeitamente sigiloso se, para todo adversário
		$\mathcal{A}$ temos:
		\begin{equation}
			Pr[PrivK^{eav}_{\mathcal{A},\Pi} = 1] = \frac{1}{2}
		\end{equation}
	\end{block}
	}
	
	\vfill \onslide<4->{\centerline{\color{red}{Demonstração!}}}
 
}

\section{One-Time Pad}

\subsection{Histórico}
\frame{
	\frametitle{\emph{One-Time Pad}}
	\begin{itemize}
		\item \emph{One-time Pad} foi um esquema de criptografia criado por Vernam em 1917 que possuia sigilo perfeito
		\item Na época não havia prova disso, nem noção do que era sigilo perfeito
		\item Shannon introduziu tais conceitos e provou que tal cifra possuia sigilo perfeito
	\end{itemize}
}

\subsection{Definição}
\frame{
	\frametitle{\emph{One-Time Pad}}
	\begin{block}{Definição}
		Seja $a \oplus b = a_1 \oplus b_1, \ldots,  a_l \oplus b_l$ o operador XOR para duas strings binárias de tamanho $l$.
		O esquema de criptogradia One-Time Pad é definido como:
		\begin{enumerate}
			\item Dado um inteiro $l>0$, $\mathcal{M},\mathcal{K}$ e $\mathcal{C}$ são iguais à $\{0,1\}^{l}$
			\item O algoritmo Gen escolhe $k\in \mathcal{K} = \{0,1\}^l$ de acordo com a distribuição uniforme
			\item Enc funciona como $c:= k \oplus m$
			\item Dec funciona como $m:= k \oplus c$
		\end{enumerate}

	\end{block}

	\begin{block}{Teorema}
		O esquema de criptografia \emph{One-Time Pad} é perfeitamente sigiloso
	\end{block}
	\vfill \onslide<2>{\centerline{\color{red}{Demonstração!}}}
}

\subsection{Críticas ao One-Time Pad}

\frame{
	\frametitle{Críticas ao \emph{One-Time Pad}}
	\begin{itemize}
		\item O tamanho da chave deve ser maior ou igual ao tamanho da mensagem cifrada: $|k| \geq  |m|$	
		\begin{enumerate}
			\item Problemático quando queremos enviar mensagens longas pois é difícil guardar chaves grandes de maneira segura
			\item Deve-se saber de antemão um limite superior do tamanho da mensagem para definir o espaço de chaves
		\end{enumerate}
		\item  É ``seguro''\footnote{Não definimos segurança ainda quando várias mensagens são cifradas} somente se
		a chave $k$ for usada uma vez, caso contrário, é possível aprender sobre o esquema
		\begin{align*}
			c \oplus c' = & (m\oplus k) \oplus(m' \oplus k)\\
			 = & m\oplus m'
		\end{align*}
	\end{itemize}

}

\section{Limitações do sigilo perfeito}

\frame{
	\frametitle{Limitações do sigilo perfeito}
	Qualquer esquema criptográfico que possua sigilo perfeito, deve ter $|\mathcal{K}| \geq |\mathcal{M}|$
	e  $|k|\geq |m|$. Não é uma característica do \emph{One-Time Pad}. É inerente à todos os esquemas criptográficos
	dessa classe


	\begin{block}{Teorema}
		Seja $\Pi=(Gen,Enc,Dec)$ um esquema criptográfico que possua sigilo perfeito sobre um espaço de
		mensagens $\mathcal{K}$. Seja $\mathcal{K}$ o espaço de chaves determinado por $Gen$. $|\mathcal{K}| \geq |\mathcal{M}|$
	\end{block}

	\vfill \onslide<2>{\centerline{\color{red}{Demonstração!}}} 
}

\frame{
	\frametitle{Limitações do sigilo perfeito}
	Companhia XYZ: ``Conseguimos criar um esquema criptográfico que é inquebrável e possuí sigilo perfeito sem usar
	chaves grandes''
	\onslide<2>{
		\begin{figure}[h!]
		\centering
		\includegraphics[scale = 0.5]{./imagens/facepalm.jpg}
		% facepalm.jpg: 456x297 pixel, 100dpi, 11.58x7.54 cm, bb=0 0 328 214
		\label{fig:facepalm}
	}
\end{figure}
}

\section{Teorema de Shannon}

\frame{
	\frametitle{Teorema de Shannon}
	Shannon foi o responsável por introduzir o conceito de sigilo perfeito.
	Ele elaborou o seguinte teorema sobre esquemas criptográficos:
	\begin{block}{Teorema}
		Seja $\Pi = (Gen,Enc,Dec)$ um esquema criptográfico sobre um espaço de mensagem
		$\mathcal{M}$ onde $|\mathcal{M}| = |\mathcal{C}| = |\mathcal{K}|$. Tal esquema
		é perfeitamente sigiloso se, e somente se:
		\begin{enumerate}
			\item $\forall k \in \mathcal{K}$ é escolhido com probabilidade $\frac{1}{\mathcal{K}}$ por $Gen$
			\item $\forall m \in \mathcal{M}$ e $\forall c \in \mathcal{C}$, existe uma única chave $k \in \mathcal{K}$
			tal que $Enc_k(m)$ da como saída $c$
		\end{enumerate}
	\end{block}
  
	\vfill{\onslide<2>{\color{red}{\centerline{Demonstração!}}}}
}

\frame{
	\frametitle{Uso do teorema de Shannon}
	\begin{itemize}
		\item Serve para uma distribuição de probabilidade genérica sobre $\mathcal{M}$
		\item Usado para provar se determinado esquema criptográfico possui sigilo perfeito
		\item Vale somente para $|\mathcal{M}| = |\mathcal{K}| = |\mathcal{C}|$
	\end{itemize}
}


\section{Conclusão}
\frame{
	 \frametitle{Conclusão}
	  \begin{itemize}
		  \item Esquema criptográficos com sigilos perfeitos são possíveis:
		  o texto cifrado não revela nada sobre o texto em claro, mesmo com adversários com poder computacional ``ilimitado''
		  \item Limitações de aplicação em seu uso, comercialmente não é muito utilizado
	  \end{itemize}
}
